package exercises.leetcode;

/**
 * <a href="https://leetcode-cn.com/problems/best-sightseeing-pair/">
 * 1014. 最佳观光组合</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。
 * <p>
 * 一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
 * <p>
 * 返回一对观光景点能取得的最高分。
 * <p>
 * 示例 1：
 * <p>
 * 输入：values = [8,1,5,2,6]
 * 输出：11
 * 解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
 * 示例 2：
 * <p>
 * 输入：values = [1,2]
 * 输出：2
 *  
 * <p>
 * 提示：
 * <li>2 <= values.length <= 5 * 104</li>
 * <li>1 <= values[i] <= 1000</li>
 *
 * @author or2
 * @date 2021年10月02日 时间: 17:02
 */
public class No1014 {
    public int maxScoreSightseeingPair(int[] values) {
        int preMax = 0, res = 0;
        for (int i = 0, valuesLength = values.length; i < valuesLength; i++) {
            int max;
            if ((max = preMax + values[i] - i) > res)
                res = max;
            int start;
            if ((start = values[i] + i) > preMax)
                preMax = start;
        }

        return res;
    }
}
